package offer

import (
	. "GoLeetcode/common"
	"math"
)

/*
时间复杂度:O(N)
空间复杂度:O(1)
*/

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func largestValues(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	res := make([]int, 0)
	level := []*TreeNode{root}
	for len(level) != 0 {
		maxVal := math.MinInt64
		var pos int
		for i, node := range level {
			if node != nil {
				if maxVal < node.Val {
					maxVal = node.Val
				}
				level = append(level, node.Left, node.Right)
			}
			pos = i
		}
		level = level[pos+1:]
		if maxVal != math.MinInt64 {
			res = append(res, maxVal)
		}
	}
	return res
}
